Quy trình quyết định Markov (MDP) cung cấp một nền tảng
toán học cho việc mô hình hóa việc
ra quyết định trong các tình huống mà kết quả là một phần
ngẫu nhiên và một phần dưới sự điều khiển của một người ra quyết định. MDP rất hữu dụng cho việc học một loạt
bài toán tối ưu hóa được giải quyết thông qua
quy hoạch động và
học tăng cường. MDP được biết đến sớm nhất là vào những năm 1950 (cf. Bellman 1957). Một cốt lõi của nghiên cứu về quá trình ra quyết định Markov là từ kết quả của cuốn sách của
Ronald A. Howard xuất bản năm 1960, Quy hoạch động và quá trình Markov. Chúng được sử dụng trong rất nhiều các lĩnh vực khác nhau, bao gồm
robot,
điều khiển tự động,
kinh tế, và
chế tạo.Chính xác hơn, một quá trình quyết định Markov là một quá trình
điều khiển ngẫu nhiên thời gian rời rạc. Tại mỗi bước thời gian, quá trình này trong một vài trạng thái s {\displaystyle s} , và người ra quyết định có thể chọn bất kỳ hành động a {\displaystyle a} nào có hiệu lực trong trạng thái s {\displaystyle s} . Quá trình này đáp ứng tại bước thời gian tiếp theo bằng cách di chuyển ngẫu nhiên vào một trạng thái mới s ′ {\displaystyle s'} , và đưa ra cho người ra quyết định một phần thưởng tương ứng R a ( s , s ′ ) {\displaystyle R_{a}(s,s')} .Xác suất mà quá trình di chuyển vào trạng thái mới của nó s ′ {\displaystyle s'} bị ảnh hưởng bởi hành động được chọn. Đặc biệt, nó được đưa ra bởi hàm chuyển tiếp trạng thái P a ( s , s ′ ) {\displaystyle P_{a}(s,s')} . Do đó, trạng thái kế tiếp s ′ {\displaystyle s'} phụ thuộc vào trạng thái hiện tại s {\displaystyle s} và hành động của người ra quyết định a {\displaystyle a} . Nhưng s {\displaystyle s} và a {\displaystyle a} đã cho, lại độc lập có điều kiện với toàn bộ trạng thái và hành động trước đó; nói cách khác, các trạng thái chuyển tiếp của một quá trình MDP thỏa mãn thuộc tính
Markov.Quá trình quyết định Markov là một phần mở rộng của chuỗi Markov; khác biệt là ở sự bổ sung của các hành động (cho phép lựa chọn) và phần thưởng (cho động cơ). Ngược lại, nếu chỉ có một hành động tồn tại cho mỗi trạng thái và tất cả các phần thưởng là giống nhau (ví dụ: zero), một quá trình quyết định Markov làm giảm một chuỗi Markov.
